package algotithm.weekendrace.leetcode242.test4;

/**
 * @author 25068
 * @Date 2021/5/23 12:05
 */
class Solution {
    class SegmentTree {
        long[] tree;
        int n;
        public SegmentTree(int len) {
            n = len;
            tree = new long[n * 2];
        }

        public void update(int pos, long val) {
            pos += n;
            tree[pos] = val;
            while (pos > 0) {
                int left = pos;
                int right = pos;
                if (pos % 2 == 0) {
                    right = pos + 1;
                } else {
                    left = pos - 1;
                }
                tree[pos / 2] = Math.max(tree[left], tree[right]);
                pos /= 2;
            }
        }

        public long sumRange(int l, int r) {
            l += n;
            r += n;
            long sum = Long.MIN_VALUE;
            while (l <= r) {
                if ((l % 2) == 1) {
                    sum = Math.max(sum, tree[l]);
                    l++;
                }
                if ((r % 2) == 0) {
                    sum = Math.max(sum, tree[r]);
                    r--;
                }
                l /= 2;
                r /= 2;
            }
            return sum;
        }
    }

    public int stoneGameVIII(int[] stones) {
        int len = stones.length;
        long[] sum = new long[len + 1];
        for (int i = 0; i < len; ++i) {
            sum[i + 1] = sum[i] + stones[i];
        }
        long max = Integer.MIN_VALUE;
        SegmentTree tree = new SegmentTree(stones.length);
        for (int i = stones.length - 1; i >= 1; --i) {
            long curDiff = sum[i + 1];
            if (i != stones.length - 1) {
                curDiff -= tree.sumRange(i + 1, stones.length - 1);
            }
            tree.update(i, curDiff);
            max = Math.max(max, curDiff);
        }
        return (int)max;
    }
}

